package com.lw.leetcode.dp.a;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 10- II. 青蛙跳台阶问题
 * 70. 爬楼梯
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/23 11:38
 */
public class ClimbStairs {

    public static void main(String[] args) {
        ClimbStairs test = new ClimbStairs();
        // 782204094
        int i = test.numWays(100);
        System.out.println(i);
    }

    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 3) {
            return n;
        }
        long a = 1;
        long b = 2;
        long c;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c % 1000000007;
        }
        return (int) b;
    }

    public int climbStairs(int n) {
        Map<Integer, Integer> map = new HashMap<>((n << 2) / 3 + 1);
        return find(n, map);
    }


    public int find(int n, Map<Integer, Integer> map) {
        int a;
        int b;
        if (n < 3) {
            return n;
        } else {
            if (map.get(n - 1) == null) {
                a = find(n - 1, map);
                map.put(n - 1, a);
            } else {
                a = map.get(n - 1);
            }
            if (map.get(n - 2) == null) {
                b = find(n - 2, map);
                map.put(n - 2, b);
            } else {
                b = map.get(n - 2);
            }
            return a + b;
        }
    }

}
